\documentclass{article}
\usepackage[utf8]{inputenc} % un package
\usepackage[T1]{fontenc}      % un second package
\usepackage[francais]{babel}  % un troisième package
\usepackage{amsmath}
\usepackage{graphicx}

\title{SIG Nomades}
\author{Alexandre Masson}
\date{10 Septembre 2013}

\begin{document}
\maketitle
\newpage
\section{10 Septembre 2013}
\paragraph{objectif}
L'objectif de ce cours, tout d'abord parlons de ce qu'on ne va pas faire, tout d'abord , on ne va pas devenir geographe, donc on ne va pas uniquement apprendre a utiliser les sig existants, mais il est bon de connaître les plus importants
\begin{itemize}
\item IGN associé à geoportail
\item OpenStreetMap
\item Google
\item PostGis
\end{itemize}

\paragraph{}
Le principal objectif est de pouvoir écrire des applications qui utilisent les sig.

\paragraph{Quelle est l'architecture d'une application SIG}
\begin{center}
\includegraphics[scale=0.5]{sigarchi.png}
\end{center}

IL existe deux parties, une plut\^ot algorithmique, une sur les SIG existant.\\\\
La matière est juste évaluée sur un projet : partir d'une carte de l'université, calculer un itinéraire, faire un peu de navigation, et le sujet va rajouter d'autres trucs.

\newpage

\section{Partie Algorithmique}
\subsection{Introduction à l'algorithmique géométrique}
\paragraph{Références} Computational geometry \bsc{Mark de Borg} (Springer).
Il existe dans un plan tout une série de polygones, et nous allons nous poser une série de questions sur ces polygones du plan .\\
J’ai envie d'écrire un programme de système de guidage : de quoi j'ai besoin? 
\begin{itemize}
\item se localiser, on veux que l'algo soit suffisamment efficace pour savoir en temps réel ou on est, 
\item visualiser une partie de la carte, tout aussi rapidement.\\\\



\end{itemize}
Je voudrais visualiser une carte en relief, quel est le problème? j'ai le relief pour un certain nombre de points, on doit faire une interpolation, soit la hauteur sur un sous ensemble de point, et je dois pouvoir faire une estimation des hauteurs partout.\\\\

Je souhaiterais combiner des cartes, ce problème est liée, au calcul de l'intersection entre deux ensembles de segments de droite. on chercher  a calculer uniquement ceux qui sont intéressant, il faut donc connaître la notion d’intéressant, ou comment calculer.\\\\

Calculer la position du distributeur le plus proche, si cette requête ne doit être appliquer d'une fois, ça va, mais si on doit recalculer souvent , on découpe le plan pour connaître par distributeur sa zone d'influence.\\\\

J’ai une carte donnée sous forme d'obstacles.

\subsection{Points et Vecteurs}
\paragraph{} ON distingues deux types d'objets: \\
point A = (a,b) (décrit par ses coordonnées)\\
un vecteur u = (x,y)//
Opérations élémentaires
\begin{itemize}
\item 2 points  = vecteur AB
\item combinaisons linéaire : u+v , $\lambda$u
\item un point + un vecteur = un nouveau point
\end{itemize}

\paragraph{}
Transformation
\begin{itemize}
\item linéaire : f vecteur -> vecteur, représentée par une matrice 2x2
\item affine : G :  qui ets une application linéaire + un point
\end{itemize}

\paragraph{Transformation élémentaire}
\begin{itemize}
\item Translation d'un vecteur $\vec{t} : A -> A+\vec{t}$
\item Homothétie de coefficient $\lambda$ : A -> $\lambda$A , $\lambda$ > 0
\item Rotation d'origine O  : $\begin{pmatrix}
Cos\theta -sin\theta \\
sin\theta cos\theta
\end{pmatrix}$ qui donne \\\\
A$\begin{pmatrix}
x\\y
\end{pmatrix}$ -> $\begin{pmatrix}
cos\theta .x  -sin\theta .y \\
sin\theta .x  +cos\theta .y
\end{pmatrix}$
\item produit scalaire et produit vectoriel
\item[---]produit scalaire $\vec{u}(x_1y_1).\vec{v}(x_2y_2) = x_1x_2 + y_1y_2$
\item[---]produit vectoriel $\vec{u} \wedge \vec{v} = x_1y_2 - x_2y_1$
\end{itemize}
\subsection{objets géométriques élémentaires}
\paragraph{Objets}
\begin{itemize}
\item Point : A
\item Segment : AB = $\forall C / C = \lambda\vec{AB}$ avec $0\leq\lambda\leq1$ 
\item Droite : un point A et une direction $\vec{u}$ , $\forall C / C = \lambda\vec{AB}$
\item Demi-droite : un point A et une direction $\vec{u}$ , $\forall C / C = \lambda\vec{AB}$ avec $0\leq\lambda$ 
\item Demi-Plan : A,$\vec{u}$ = ${\forall C / \vec{u}\wedge\vec{AC}\geq0}$
\item Polyèdre : suite de point $ A_0,A_1,A_2,...,A_{n-1}$ sans croisement
\end{itemize}

À partir de ces objets de bases on va traiter des petits problèmes\\\\
\begin{itemize}
\item distance d'un point à une droite, facile, le produit vectoriel nous donne directement la réponse
\item projection d'un point sur une droite suivant une directions, il faut poser ces contraintes,  par exemple, les deux vecteurs ne sont pas colinéaires, ensuite manipuler les faits pour trouver $\lambda$ a partir de produits vectoriels existants, dont on connais la formule, (cf plus haut)
\item intersection de deux segments : contraintes de demi plan
\item test:point $\in$ polyèdre : on teste si la demi droite horizontale d'origine mon point A, on compte combien de fois on intersecte le polyèdre, si pair: alors extérieur, si impair, alors intérieur.
\item surface d'un polyèdre : $\sum_{i=0}^{n-1}\vec{OA_i}\wedge\vec{OA_{i+1}}$
\end{itemize}

\newpage
\section{17 Septembre 2013}
\subsection{Intersection de segments}

\paragraph{le problème}
Nous avons un ensemble de segments, nous souhaitons trouver toutes les intersections de ces segments.\\
\textbf{Algorithme simple :} O($n^2$) , mais nous souhaitons avoir un résultat rapide, car il y a souvent un grand nombre de segments\\
\textbf{Algorithme moins simple :} O(nlogn)+O(klogn) avec k le nombre d'intersections.\\

\paragraph{principe de l'algorithme}
\begin{itemize}

\item[•] Ensemble donné de points d’événements : on l’appelle queue, 
\begin{itemize}
\item[-] On cherche le premier
\item[-] On ajoute le point
\end{itemize}
\item[•] Ligne
\begin{itemize}
\item[-] Ajout(Segment)
\item[-] Modification de la ligne
\item[-] Suppression
\item[-] Gauche(Segment)
\item[-] Droite(Segment)
\end{itemize}
\end{itemize}
-> la relation Gauche/droite nécessite la mise ne place d'un arbre binaire équilibré, et la notion d'ordre entre les segments en fonction de la position de la ligne
\newpage
\section{24 septembre 2013}
\paragraph{Projet}
Plan de l'université, calcul de chemin entre deux bâtiments, calculer une chemin entre un point et un bâtiment, \\
faire des choses intéressantes en plus, \\
il faut faire une version pure android, version locale, (choisir un format des données, comment les stocker dans le téléphone, il faut reprogrammer les algorithmes de POSTGIS dans le téléphone, il va falloir superposer la carte des bâtiments et celle des chemins.)\\\\
et une version avec un webservice, POSTGIS (dans cette configuration, il faut délocaliser les calculs)


\paragraph{Problèmes}
le principal problème c'est de bien comprendre l'algorithme décrit dans le livre, \\
\begin{itemize}
\item[1] tout d'abord, il considère que les segments sont ouverts, donc les extrémités n'appartiennent pas aux segments
\item[2] Approximation, les float contiennent des arrondit qui dérangent les calculs, on peut résoudre un peu ce problème en considérant des points tres proches comme égaux
\end{itemize} 

\subsection{Localisation}
\paragraph{Problème}
\begin{itemize}
\item Entrée : découpage d'une zone par des segments, sans intersection, coordonnées (x,y)
\item Sortie : donner la zone
\end{itemize}

\begin{itemize}
\item Le découpage est fixé
\item temps de localisation petit (O(log n) en moyenne)
\item minimiser l'espace mémoire
\end{itemize}

\subsection{Localisation simple}
\begin{itemize}
\item Polyèdre convexe
\begin{itemize}
\item on découpe le polyèdre en moitié , on considère des sections, on trouve par dichotomie la section qui correspond au point recherché, et ensuite on regarde si il est entre les segments qui constitue la section (un en haut et un en bas) 
\end{itemize}
\item Cas quelconque, mais espace en O(n carré)

\item \textbf{Algorithme Astucieux}
\begin{itemize}
\item[HYPOTHÈSE] on a jamais deux points sur la même verticales
\item par point, on construit deux segments, celui du dessus et celui du dessous, celui des deux qui ne renvoi pas vers le cadre doit arrêter au prochain segment du polyèdre qu'il croise.
\end{itemize}
\end{itemize}
\newpage
\section{8 Octobre 2013}

\paragraph{Algorithme d'arbre de décision}
on considère un espace rempli de polyèdres, on définit des zones dedans, on trace des "verticales" à chaque point de notre espace, puis on fait une recherche dichotomique dans l'espace, on cherche à quelle abscisse le point appartient, et soit on obtient des feuilles (souvent la zone de dehors) ensuite on refais une recherche dans la deuxième dimension, en comparant la position en ordonnée de notre point avec les segments(au dessus ou en dessous)  et encore une fois en fonction des choix on saura où nous sommes.\\
\textbf{ATTENTION} ON N4A JAMAIS L4EGALIT2 A CAUSE DES ERREURS DE CALCULS TOUTEFOIS IL PEUT ÊTRE PERTINENT DE RENVOYER UN POINT PLUTÔT QU4UNE ZONE \\\\

\subsection{Triangulation de polyèdre}
Algorithme simple $O(n^2)$ \\
Algorithme moins simple $O(n.log(n))$
\paragraph{Algorithme simple} on sais déjà que le nombre de triangle est de n-2 si n est le nombre de segments.\\
\textbf{principe : } Trouver des diagonales pour couper en 2 le polyèdre\\\textbf{Problème : } Trouver une diagonale 
\begin{itemize}
\item v est le plus a gauche de uw.
\item tester qu'uw diagonale est l'élément le plus a gauche de uw
\item découper en deux
\item Quand il reste trois points, condition d’arrêt : c'est un triangle
\end{itemize}

\paragraph{Algorithme moins simple} On  va utiliser des structures de données un petit peu plus complexe. Mais cela nous permet de gagner en complexité.\\
l'idée de cet algorithme est de découper le polyèdre en polyèdres plus simples, car on sais ensuite les trianguler en temps linéaire\\
\textbf{Principe : }
\begin{itemize}
\item Découper le polyèdre en polyèdres y-monotones
\item Chacun des polyèdres monotones, se décompose en triangles en temps linéaire.
\item Définition : un polyèdre est monotone par rapport à une ligne l si $\forall A,B$ points dans le polyèdre tel que $AB\perp l$ alors $[AB] \subseteq$ polyèdre
\end{itemize}

Il existe plusieurs types de points
\begin{itemize}
\item point régulier $e_i$ : $(e_{i-1}.y-e_i.y).(e_{i+1}.y-e_i.y) <0$
\item point de départ : point tel que ces deux voisins sont plus bas que lui, et tourner vers l’intérieur (sens anti-horaire)
\item on suppose qu'il n'y a pas de segments horizontaux, sinon  on considère le point droite plus haut que celui de gauche
\item point de fin : point tel que ces deux voisins sont plus haut , et il tourne vers l’intérieur
\item point de découpage
\item point de fusion
\item si aucun point de fusion ou de découpage, y-monotone
\end{itemize}
\paragraph{Structure de données}
\begin{itemize}
\item Ensemble de points de haut en bas
\item Ensemble ordonné de segments coupant une horizontale
\end{itemize}

\paragraph{Algorithme : }
Initde Q = {point} et T = $\emptyset$\\
tant que Q $\neq \emptyset$\\
faire $v_i = Q.pop();$\\
appliquer une méthode à $v_i$ en fonction de sont type
\paragraph{HandleStartVertex($v_i$)}
\begin{itemize}
\item[1] Mettre $e_i$ dans T (avec $e_i$ = $\bar{v_i}\bar{v_{i+1}}$)
\item[2] helper($e_i$)= $v_i$
\end{itemize}

\paragraph{HandleEndVertex($v_i$)}
\begin{itemize}
\item[1] si helper($e_{i-1}$) est une merge vertex alors\\InsererDiagonale $v_i -> helper(e_{i-1})$
\end{itemize}

\paragraph{HandleSplitVertex}
\begin{itemize}
\item[1] $e_j$ segment à gauche de $v_i$\\InsererDiagonale $v_i -> helper(e_j)$\\helper($e_j$) <- $v_i$\\Inserer $e_i$ dans T et helper($e_i$)=$v_i$
\end{itemize}

\paragraph{HandleMergeVertex($v_i$)}
\begin{itemize}
\item si helper($e_{i-1}$) est un mege" alors insérer diagonale $v_i$ -> helper($e_{i-1}$)\\Efface $e{i-1}$ dans T\\$e_j$ <- gauche de $v_i$\\si helper($e_j$) est "merge" alors insérer diagonale $v_i$ -> helper($e_j$)\\
helper($e_j$) <- $v_i$

\paragraph{HandleRegularVertex($v_i$)}
\begin{itemize}
\item[-] si l'intérieur est à droite alors\\ si helper($e_{i-1}$) est un "merge" alors\\ insérer diagonale $v_i$->helper($e_{i-1}$)\\
Efface $e_{i-1}$ de T \\
Insérer $e_i$ dans T et helper($e_i$)<-$v_i$
\item[-]sinon\\$e_j$ gauche de $v_i$\\si helper($e_j$) est une "merge" alors\\insérer la diagonale$v_i$->helper($e_j$)\\helper($e_j$)=$v_i$
\end{itemize}
\end{itemize}
\newpage
\section{14 Octobre}
\subsection{Introduction}
\paragraph{} SIG: système d'informations géographiques\\
SI : système de communication permettant de communiquer et traiter de l'information
\paragraph{Définitions} 
Analyse, modélisation, affichage, relatif aux données spatiales\\
composé de
\begin{itemize}
\item Acquisition
\item Stockage
\item Aide à la décision
\item Interrogation(IHM), toujours de quoi faire, soit SQL, interface en client lourd ou web
\end{itemize}
Nous allons utiliser POSTGIS, qui marche au dessus de POSTGRESQL.

\paragraph{Les grandes fonctions attendues}
\begin{itemize}
\item[où? ] la localisation peut prendre différentes formes, soit poser des coordonnées et un rayon et renvoyer tout ce qui s'y trouve, soit dans une ville
\item[quand? ] le monde étant rarement figé, il va falloir prendre en compte la notion de temps pour savoir comment les choses évoluent, ou vont évoluer
\item[comment? ] quelles sont les relations spatiales qui existent? on parle de Buffer pour une zone géographique étendue (exemple : un point et une zone de 5km de rayon autour).
\item[quoi? ] on va greffer au moins un niveau pour stocker à quoi correspondent les choses, plusieurs informations associées à des objets qui peuvent être différents
\item[et si? ] ça peut être de l'aide à la décision pour faire une projection de l'évolution, etc...
\end{itemize}
On utilise différentes couches en SIG, des informations géométriques et d'autres couches avec les informations associées, ces couches s'appellent des layers. 
\newpage
\subsection{une brève histoire des SIGs}
\paragraph{Évolution}
Déja : on est passé d'un niveau pro à une dimension grand public, surtout à cause du coût.\\
les SIG grand public , comme Google Earth, GEOportal, OpenStreetMap.\\
On est aussi passé de systèmes propriétaires à des systèmes ouverts(exemple : ERSI qui a fait ArcGis, MapInfo d'une société plus petite), et on a eu un effort important depuis des années sur les systèmes ouverts.\\
MapServer, GéoServer(récent, on va s'en servir), on lui colle une BD derrière, et nous devons traiter ce qu'il nous renvoie.\\
on va utiliser OpenLayers, une petite application qui va nous permettre de  manipuler des petites cartes.\\
Coté client lourd, on a aussi geoTools, bibliothèque java qui faire permettre de générer facilement des cartes, QGis.\\\\

Données propriétaires -> Données ouvertes , OpenData(data.gouv.fr) initiative de données publiques ouvertes, disponible gratuitement, initié par la BOURGOGNE( pow pow pow repwesente!!!). le meilleur exemple est celui d'OpenStreetMap. Ça va du contenu ouvert au format , gros effort de normalisation.\\\\

passage du fixe au nomade. que fait on circuler, encore des segments à traiter, ou seulement des informations en terme de pixels, se pose aussi la problématique de la géolocalisation.\\\\

Application pro -> application de type jouet (ou est la plus proche application)
\subsection{Nos Objectifs}
\paragraph{} 
\begin{itemize}
\item avoir une culture minimale en SIG
\item une connaissance de l'existence des outils pro
\item une pratique des outils libres
\item la capacité de mettre en place une chaîne complète (depuis BD -> interface web -> terminal nomade)
\item l'identification de grandes sources de données ouvertes
\end{itemize}

\subsection{Information Géographique}
\paragraph{Nature}
\begin{itemize}
\item géométrique
\item sémantique
\end{itemize}
Quelles sont les formes d'expression disponible
\begin{itemize}
 \item carte : visuel qui contient des points/traits/textes/zones, mais aussi un choix de symboles pour expliquer les choses, leur visibilité(ou non). symbologie : études des signes dans les sciences sociales
 \item texte : permet de décrire les choses différemment
 \item iconique : tout ce qui va être image/photo (ex: satellite)
\end{itemize}
\section{17 Octobre}
\paragraph{Information géographique numérique} elle va pouvoir prendre plusieurs formes. il existe des façon de représenter des cartes, le mode vecteur, et le mode raster(maillage). Dans le premier cas on à de segments classiques, le mode raster maille l'espace en zone de même taille (pixels) et donne à chaque zone des informations complémentaires. L'avantage du vectorisé, c'est que l'on a pas de problème d'échelle, a chaque fois on interprète des informations géométriques, l'autre avantage c'est que c'est compact. Son principal inconvénient c'est qu'il faut retraiter à chaque fois que l'on en a besoin.\\\\

le raster fais appel à la notion de tuillage, il recoupe les zones en carré, et recharge seulement si besoin.

\begin{tabular}{|c|c|c|}
\hline 
  & + & - \\ 
\hline 
VECTORIEL & stockage compact & reconstruction coûteuse\\ &indépendant du zoom & saisie/prétraitement \\ & & effort indexation\\
\hline 
RASTER & interprétation immédiate & stockage plus lourd \\ & indexation spatiale directe & pb zoom \\ 
\hline 
\end{tabular} 

indexation par quadTree : indexation bidimensionnel, on découpe chaque zone en récursivement, on peut donc indexer des informations et des relations spatiales entre des zones, on retrouve un arbre en 3D qui regroupe les zones.

\subsection{Localisation}
\subsubsection{Mode géométrique} 
\paragraph{} référentiel qui doit être direct, qui à un centre, x passe par le méridien de Greenwich, y, z (vertical).

\paragraph{}
le point d'origine est le centre des masses de la terre. La Terre est représentée par une Ellipsoïde, que l'on appelle Ellipsoïde de référence (car la terre est aplatit aux pôles). On fournit soit des coordonnées directe, soit la latitude (angle du point avec $\vec{x}$ vers Z), la longitude(angle avec l'axe $\vec{x}$ vers $\vec{y}$), et l'altitude par rapport au niveau de la mer.

\paragraph{}
La Terre n'as pas un contour régulier, les ellipsoïde peuvent être différentes en fonction des régions.\\
le WGS(World Geodesic System) a produit trois référentiel, on utilise celui de 1984.

\paragraph{}
On calcule l'altitude à partir du géoïde, qui est une zone d'équi-pesanteur, car comme l’ellipsoïde est centré sur les masse, on obtient le niveau des mers.\\
Notre carte est composé d'un 0 noté en bas a droite de la carte, avec un axe vers le nord, un axe vers l'est, et les coordonnées sont données en fonction\\
$o_e = f(\phi,\lambda)$\\
$o_n = g(\phi,\lambda)$\\
Points géodésiques : point mesurés très précisément sur Terre et qui sers de référence pour les calculs. On les positionne et on passe régulièrement pour mesurer. Ce qui permet parfois de récupérer son altitude, par interpolation. Les coord sont acquise avec GPS, se qui est très précis.

\subsection{Mode indirect}
\paragraph{} le bon exemple est l'adresse postale, car un codage particulier nous indique une position, mais sans coordonnées. Un autre bon exemple est un numéro de parcelle, on connais toutes les parcelles, et avec le numéro on peux se retrouver. Il existe des codes européen pour les communes, et un autre découpage, IRIS-2000 qui va découper le territoire français en îlot, avec des caractéristiques spécifiques, par exemple la nature du terrain(habitation,activité, autres).

\subsection{Structuration et modèle conceptuel}
\paragraph{Abstraction} on va simplifier notre structure (par pertinent de représenter tous les grains de sables de la plage).
\paragraph{formes}
\begin{itemize}
\item Point
\item Ligne
\item Surface
\item Surface à trou
\end{itemize}

\paragraph{relations spatiales} entre les éléments géométrique du modèle.\\
le relation entre les zones : adjacence, inclusion, intersection(ces trois là sont vraies ou fausses), proximité(dépend des paramètres).\\
On peut représenter nos forme, sommet = points, arc=segment, faces= surfaces, on définit des relations
\begin{itemize}
\item arc <-> sommet : {a pour début, a pour fin}
\item arc <-> face : {a pour face de gauche, a pour face de droite}
\item face <-> face : {inclus dans}
\end{itemize}

\paragraph{Niveau sémantique}
\begin{itemize}
\item caractéristique intrinsèques (ex: type de terrain) (intrinsèque: ça depend que de lui)\\caract de relation (ex: champs voisins)
\item champs vectoriel : (ex: si je prend les parcelles, je veux leur taille, info globales au champs
\end{itemize}
\paragraph{les grandes sources de données}
référentiel national
\begin{itemize}
\item grande échelle : topographie(route,etc...)/photo/parcelles/adresse
\item moyenne échelle : état des routes, infos de type occupation des sols
\item petite échelle : info niveau commune
\end{itemize}

\end{document}